/**
 * 75. 颜色分类
 * https://leetcode-cn.com/problems/sort-colors/
 */
const { displayBaseArray } = require('../../libs/public');

// /**
//  * @param {number[]} arr
//  * @param {number} begin
//  * @param {number} end
//  */
// function quickSort(arr, begin, end) {
//   if (begin >= end) return;
//   let left = begin;
//   let right = end;
//   const base = arr[left];
//   while (left < right) {
//     while (left < right && arr[right] >= base) {
//       right -= 1;
//     }
//     arr[left] = arr[right];
//     while (left < right && arr[left] <= base) {
//       left += 1;
//     }
//     arr[right] = arr[left];
//   }
//   arr[left] = base;
//   quickSort(arr, begin, left - 1);
//   quickSort(arr, left + 1, end);
// }
//
// /**
//  * @param {number[]} nums
//  * @return {void} Do not return anything, modify nums in-place instead.
//  */
// function sortColors(nums) {
//   quickSort(nums, 0, nums.length - 1);
// }

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
function sortColors(nums) {
  let zeroCount = 0;
  let oneCount = 0;
  let twoCount = 0;
  nums.forEach((num) => {
    switch (num) {
      case 0:
        zeroCount += 1;
        break;
      case 1:
        oneCount += 1;
        break;
      case 2:
        twoCount += 1;
        break;
      default:
        break;
    }
  });
  let i = 0;
  for (let j = 0; j < zeroCount; j += 1, i += 1) {
    nums[i] = 0;
  }
  for (let j = 0; j < oneCount; j += 1, i += 1) {
    nums[i] = 1;
  }
  for (let j = 0; j < twoCount; j += 1, i += 1) {
    nums[i] = 2;
  }
}

let nums;

nums = [2, 0, 2, 1, 1, 0];
sortColors(nums);
console.log(displayBaseArray(nums) === '[0,0,1,1,2,2]');

nums = [2, 0, 1];
sortColors(nums);
console.log(displayBaseArray(nums) === '[0,1,2]');

nums = [2];
sortColors(nums);
console.log(displayBaseArray(nums) === '[2]');

const origin = [];
for (let i = 0; i < 1e4; i += 1) {
  origin.push(Math.floor(3 * Math.random()));
}
nums = [...origin];
const answer = [...origin].sort((a, b) => a - b);
sortColors(nums);
console.log(displayBaseArray(nums) === displayBaseArray(answer));
